1. Field of the Invention
The present invention relates in general to a conservative event-synchronization protocol, time-based synchronization, which is particularly suited for parallel discrete event simulation of mobile ad hoc wireless networks.
2. Description of the Background Art
A mobile ad hoc wireless network (MANET) is a collection of mobile wireless nodes that form a temporary network without any infrastructure or centralized control. Researchers typically cite three uses for MANETs: emergency situations, military operations, and sensor networks. MANETs used in such situations could conceivably contain several thousand nodes. Simulators that evaluate MANETs must therefore be capable of simulating large-scale networks. Researchers wishing to quickly simulate such networks typically use parallel discrete-event simulators (PDES). These simulators all use conservative event-synchronization protocols to ensure that they produce the same results as a sequential simulator would.
A parallel discrete-event simulator can be considered to be composed of N logical processes, LP0; : : : ; LPN_1; which communicate by sending messages containing time-stamped events. Each logical process has the following components: (1) the state variables that correspond to the part of the simulated physical system that the LP represents, (2) a time-ordered event queue, and (3) a local clock whose value equals the timestamp of the LP's most-recently-executed event.
An LP in a simulation using a conservative event-synchronization protocol must obey the local causality constraint. If such an LP has an event with timestamp T at the head of its event queue, it cannot execute this event until it is sure that it will not later receive a message with a timestamp earlier than T. As an example, in a simulation using the known null-message protocol, an LP receives messages via incoming-message queues (one for each LP that can send messages to the LP in question). Each such queue has a “clock,” which equals the timestamp of the last message that the destination LP removed from the queue. Because the messages sent on each queue are guaranteed to have non-decreasing timestamps, an LP will become sure that it can execute the event at the head of its event queue when the clocks of all of its incoming-message queues are later than or equal to T. To ensure progress, LPs send time-stamped null messages, which do not contain actual events, but instead contain an implicit promise that the senders will not send to the receivers any messages with timestamps earlier than the timestamps of the null messages.
A MANET simulator typically uses two events per node to model a wireless transmission. The first represents the beginning of the transmission, and the second represents the end of the transmission. Consider an example with three nodes, node A, node B, and node C, which are simulated by LPA, LPB and LPC. Say that node A transmits a packet at simulated time 5 μs. The packet will reach nodes B and C only after some time, called the propagation delay, has elapsed. Assume that the propagation delay from node A to node B is 2 μs, and from node A to node C is 3 μs. The simulator will use three events to simulate the beginning of the transmission of the packet: one for node A with timestamp 5 μs, one for node B with timestamp 5+2=7 μs, and one for node C timestamp 5+3=8 μs. In a parallel simulator, LPA will send the events for nodes B and C to LPB and LPC, respectively.
The second event at each node represents the end of the transmission. Say that the transmission of the packet lasts for 100 μs; LPA; LPB; and LPC will schedule transmission-ending events with timestamps 105 μs, 107 μs, and 108 μs, respectively. Each logical process schedules its transmission-ending event itself. Neither LPB nor LPC would receive a message from LPA telling it to simulate the end of the transmission. Instead, the initial messages contain fields indicating the duration of the simulated transmission.
In most MANET simulators, an LP performs the radio calculations for a given transmission, such as determining path loss and fading, when it executes the event representing the beginning of a transmission. If an LP executes an event representing the beginning of another transmission before simulating the end of the first transmission, then it must decide whether it should simulate a collision. This decision usually depends on the signal strengths of the two transmissions and some characteristics of the simulated receiver's radio.
A drawback to know MANET simulation protocols, such as the null-message protocol, is that the speed at which an LP can execute an event depends on the rate at which the LP receives messages from other LPs in the network. For small networks, such limitations are not particularly burdensome. However, for very large networks with hundreds or even thousands of nodes, such limitations can dramatically increase the amount of time necessary to run a network simulation.